๐งท ๋นํธ๋ง์คํฌ
ํ๋์ ๋ชจ๋ CPU๋ ์ด์ง์๋ฅผ ์ด์ฉํด ๋ชจ๋ ์๋ฃ๋ฅผ ํํํ๊ณ , ์ด๋ ์ด์ง๋ฒ ๊ด๋ จ ์ฐ์ฐ์ ์์ฃผ ๋นจ๋ฆฌ ์ฒ๋ฆฌํ ์ ์๋ค๋ ์ฅ์ ์ด ์๋ค. ์ด์ ๊ฐ์ ํน์ฑ์ ์ด์ฉํด ์ ์์ ์ด์ง์ ํํ์ ์๋ฃ ๊ตฌ์กฐ๋ก ์ฐ๋ ๊ธฐ๋ฒ์ ๋งํ๋ค.
์งํฉ์ ์์๋ค์ ๊ตฌ์ฑ ์ฌ๋ถ๋ฅผ ํํํ ๋ ์ ์ฉํ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๐ช ์ฅ์
๋ ๋น ๋ฅธ ์ํ ์๊ฐ
- ๋นํธ ๋ง์คํฌ ์ฐ์ฐ์ ์ ๊ตฌํ๋๋ ๊ฒ์ด ๋ง์ ๋ค๋ฅธ ์๋ฃ ๊ตฌ์กฐ๋ณด๋ค ํจ์ฌ ๋นจ๋ฆฌ ๋์ํ๋ค.
- ๋ฌผ๋ก ๋นํธ๋ง์คํฌ๋ฅผ ์ฌ์ฉํ ์ ์๋ค๋ ๋ง์ ์์์ ์๊ฐ ๋ง์ง ์๋ค๋ ์๋ฏธ์ด๋ฏ๋ก, ์์ฒญ๋๊ฒ ํฐ ์๋ ํฅ์์ ์๋๋ค.
๊ฐ๊ฒฐํ ์ฝ๋
- ๋ค์ํ ์งํฉ ์ฐ์ฐ๋ค์ ๋ฐ๋ณต๋ฌธ ์์ด ํ ์ค์ ์ธ ์ ์์ด ์งง์ ์ฝ๋๋ฅผ ์์ฑํ ์ ์๋ค.
๋ ์์ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋
- ๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ๋ ์ ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํด ํํํ ์ ์๋ค.
- ์ด๋ก ์ธํด ๋ ๋ง์ ๋ฐ์ดํฐ๋ฅผ ๋ฏธ๋ฆฌ ๊ณ์ฐํด์ ์ ์ฅํด ๋ ์ ์๊ฒ ๋๋ค.
์ฐ๊ด ๋ฐฐ์ด์ ๋ฐฐ์ด๋ก ๋์ฒด
- ์งํฉ์ ๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ก ํํํ ์ ์๋ค.
DP๋ ์์ด ๋ฑ ๋ฐฐ์ด ํ์ฉ๋ง์ผ๋ก ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ํด๊ฒฐ
๐ช ๋นํธ๋ง์คํน ํ์ฉ
0๊ณผ 1๋ก flag ํ์ฉํ๊ธฐ
[1,2,3,4,5] ๋ผ๋ ์งํฉ์ด ์๋ค๊ณ ๊ฐ์ ํ๋ค. ์ฌ๊ธฐ์ ์์๋ก ๋ช ๊ฐ๋ฅผ ๊ณจ๋ผ ๋ฝ์ ํ์ธํด์ผ ํ๋ ์ํฉ์ด ์ฃผ์ด์ก๋ค. (๋ถ๋ถ ์งํฉ์ ์๋ฏธ)
{1}, {2}, ... , {1,2}, {1,2,5}, {1,2,3,4,5}
๋นํธ๋ง์คํน์ ํตํด, ๊ฐ ์์๋ฅผ ์ธ๋ฑ์ค์ฒ๋ผ ํํํ์ฌ ํจ์จ์ ์ธ ์ ๊ทผ์ ํ ์ ์๋ค.
[1,2,3,4,5] -> 11111
[2,3,4,5] -> 11110
[1,2,5] -> 10011
[3] -> 00100
์ด๋ฌํ 2์ง์๋ฅผ 10์ง์๋ก ๋ณํํ์ฌ ๋ถ๋ถ์งํฉ์ ์ ์๋ฅผ ํตํด ๋ํ๋ด๋ ๊ฒ๋ ๊ฐ๋ฅํ๋ค.
11111-> 10์ง์ ๋ณํ ->31
์ด๋ก์จ, ํด๋น ๋ถ๋ถ์งํฉ์ i ๋ฅผ ์ถ๊ฐํ๊ณ ์ถ๋ค๋ฉด i ๋ฒ์งธ ๋นํธ๋ฅผ 1๋ก ๋ฐ๊ฟ์ฃผ์ด ํํํ ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๋ ๋นํธ ์ฐ์ฐ์ ์ฌ์ฉํ๋ค.
๐ช ๋นํธ ์ฐ์ฐ
AND(&): ๋์ํ๋ ๋ ๋นํธ๊ฐ ๋ชจ๋ 1์ผ๋๋ง 1์ ๋ฐํOR(|): ๋์ํ๋ ๋ ๋นํธ ์ค ํ๋๋ผ๋ 1์ผ๋ 1์ ๋ฐํXOR(^): ๋์ํ๋ ๋ ๋นํธ๊ฐ ์๋ก ๋ค๋ฅผ ๋๋ง 1์ ๋ฐํNOT(~): ๋นํธ ๊ฐ์ ๋ฐ์ ํ์ฌ ๋ฐํ-
SHIFT(>>, <<): ์ผ์ชฝ ํน์ ์ค๋ฅธ์ชฝ์ผ๋ก ๋นํธ๋ฅผ ์ฎ๊ฒจ ๋ฐํ- ์ผ์ชฝ SHIFT (
A << B) :A * 2^B - ์ค๋ฅธ์ชฝ SHIFT (
A >> B) :A / 2^B
- ์ผ์ชฝ SHIFT (
[์ผ์ชฝ] 0001 โ 0010 โ 0100 โ 1000 : 1 โ 2 โ 4 โ 8
[์ค๋ฅธ์ชฝ] 1000 โ 0100 โ 0010 โ 0001 : 8 โ 4 โ 2 โ 1
๐ช ์์ ๋ฅผ ํตํ ๊ตฌํ
ํผ์์ง์ด ์๋ค. ์ฌ๊ธฐ์๋ 0๋ถํฐ 19๊น์ง์ ๋ฒํธ๋ฅผ ๊ฐ๋ ์ค๋ฌด ๊ฐ์ง์ ํ ํ์ด ์๊ณ , ์ฃผ๋ฌธ ์ ํ ํ์ ๋ฃ๊ฑฐ๋ ๋บ ์ ์๋ค.
- ๊ทธ๋ ๋ค๋ฉด ํ ํผ์์ ์ ๋ณด๋ ์ค๋ฌด ์ข ๋ฅ์ ์์๋ง์ ๊ฐ์ง๋ ์งํฉ์ผ๋ก ํํํ ์ ์๋ค.
- ์ด๋ฅผ
boolean[]์ผ๋ก ํํํ ์๋ ์์ง๋ง, ๋นํธ๋ง์คํน์ ์ฌ์ฉํ๋ค.
๊ณต์งํฉ๊ณผ ๊ฝ ์ฐฌ ์งํฉ
- ํ ํ์ ์ฌ๋ฆฌ์ง ์์ ํผ์์ ๋ชจ๋ ํ ํ์ ์ฌ๋ฆฐ ํผ์๋ฅผ ํํํ๋ ค๋ฉด ์๋์ ๊ฐ์ด ํ ์ ์๋ค.
// ํ ํ์ด ์๋ ํผ์
int emptyPizza = 0;
// ์ค๋ฌด ๊ฐ์ ํ ํ์ ๋ชจ๋ ์ฌ๋ฆฐ ํผ์
int fullPizza = (1 << 20) - 1;
1 << 20์ 1๋ค์ 20๊ฐ์ 0์ด ์๋ ์ ์์ด๋ฏ๋ก, ์ฌ๊ธฐ์ 1์ ๋นผ๋ฉด 20๊ฐ์ ๋นํธ๊ฐ ๋ชจ๋ ์ผ์ง ์ ์๋ฅผ ์ป์ ์ ์๋ค.
์์ ์ถ๊ฐ
- ์งํฉ์ ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ์ฐ์ฐ์ ์์๋ฅผ ์ถ๊ฐํ๊ณ ์ญ์ ํ๋ ๊ฒ์ด๋ค.
- ๋นํธ๋ง์คํฌ๋ฅผ ์ฌ์ฉํ ์งํฉ์์ ์์๋ฅผ ์ถ๊ฐํ๋ค๋ ๊ฒ์ ํด๋น ๋นํธ๋ฅผ ํจ๋ค๋ ์๋ฏธ์ด๋ค.
// ํ ํ ๋ชฉ๋ก์ p๋ฒ ํ ํ์ ์ถ๊ฐํ๊ณ ์ถ์ ๊ฒฝ์ฐ
toppings |= (1 << p);
1 << p๋ p๋ฒ์งธ ๋นํธ๋ง ์ผ์ง ์ ์์ด๋ค.- ์ด๋ฏธ
toppings์ p๋ฒ ํ ํ์ด ์ถ๊ฐ๋ ๊ฒฝ์ฐ ๊ฐ์ ๋ณํ์ง ์๋๋ค.
์์ ์ญ์
// ํ ํ ๋ชฉ๋ก์์ p๋ฒ ํ ํ์ ์ญ์ ํ๊ณ ์ถ์ ๊ฒฝ์ฐ (ํ ํ ๋ชฉ๋ก์ p๋ฒ ํ ํ์ด ์์ด์ผ ํจ)
toppings -= (1 << p);
// ํ ํ์ด ์์ ๋๋ ์ ์์ ์ผ๋ก ๋์ํ๋ ์ญ์
toppings &= ~(1 << p);
์์ ํฌํจ ์ฌ๋ถ ํ์ธ
- ํ ํ ๋ชฉ๋ก์ ์ํ๋ ํ ํ์ด ์ ์ถ๊ฐ๋์๋์ง ํ์ธํ๋ค.
if ((toppings & (1 << p)) == (1 << p))
System.out.println("Topping is in!");
&์ฐ์ฐ์ ๊ฒฐ๊ณผ๊ฐ์ 0 ๋๋1 << p์ด๋ค.
์์์ ํ ๊ธ
- ํด๋น ๋นํธ๊ฐ ์ผ์ ธ ์์ผ๋ฉด ๋๊ณ , ๊บผ์ ธ ์๋ค๋ฉด ํจ๋ค.
XOR์ฐ์ฐ์ ์ฌ์ฉํ๋ค.
toppings ^= (1 << p);
์งํฉ์ ํฌ๊ธฐ ๊ตฌํ๊ธฐ
- ๊ฐ์ฅ ๊ฐ๋จํ ๋ฐฉ๋ฒ์ ๊ฐ ๋นํธ๋ฅผ ์ํํ๋ฉด์ ์ผ์ ธ ์๋ ๋นํธ์ ์๋ฅผ ์ง์ ์ธ๋ ๋ฐฉ๋ฒ์ด๋ค.
- ํ์ง๋ง JAVA์์๋ ์ด์ ๊ด๋ จ๋ ๋ด์ฅ ๋ช ๋ น์ด๋ฅผ ์ ๊ณตํ๋ค.
System.out.println(Integer.bitCount(toppings));
์ต์ ์์ ์ง์ฐ๊ธฐ
- ์ต์ ์์๊ฐ ๋ฌด์์ธ์ง ์๊ด์์ด ์ง์ฐ๋ ์ฐ์ฐ์ด ํ์ํ ๋ ์ ์ฉํ๋ค.
toppings &= (toppings - 1);
toppings - 1 ์ ์ด์ง์ ํํ์ ์๊ฐํด๋ณด๋ฉด, ์ด๋ toppings ์์ ์ผ์ ธ ์๋ ์ตํ์ ๋นํธ๋ฅผ ๋๊ณ , ๊ทธ ๋ฐ์ ๋นํธ๋ค์ ์ ๋ถ ํจ ์ปท์ด๋ค.
- ๋ฐ๋ผ์ ๋ ๊ฐ์ AND ์ฐ์ฐํ๋ฉด ์ตํ์ ๋นํธ์ ๊ทธ ์ดํ์ ๋นํธ๋ค์ ์ ๋ถ 0์ด ๋๋ค.
- 40(10 1000)๊ณผ 39(10 0111)์ AND ์ฐ์ฐํ๋ฉด 32(10 0000)๋ก ์ตํ์ ๋นํธ๊ฐ ๊บผ์ง ๊ฒ์ ํ์ธํ ์ ์๋ค.
๋ชจ๋ ๋ถ๋ถ ์งํฉ ์ํ
- ์ฃผ์ด์ง ์งํฉ์ ๋ชจ๋ ๋ถ๋ถ ์งํฉ์ ์ํํ ๊ฒฝ์ฐ๋ ์ ์ฉํ๋ค.
for (int subset = pizza; subset; subset = ((subset - 1) & pizza)) {
// subset์ pizza์ ๋ถ๋ถ ์งํฉ
}
(subset - 1) & pizza์์,subset - 1๋ก ์ผ์ ธ ์๋ ์ตํ์ ๋นํธ๊ฐ ๊บผ์ง๊ณ , ๊ทธ ๋ฐ์ ๋นํธ๋ค์ ์ ๋ถ ์ผ์ง๊ฒ ๋๋ค. ์ด ๊ฒฐ๊ณผ์pizza์ ๊ต์งํฉ์ ๊ตฌํ๋ฉด ๊ทธ ์คpizza์ ์ํ์ง ์๋ ๋นํธ๋ค์ ๋ชจ๋ ๊บผ์ง๊ฒ ๋๋ค.- ์ด ์ฐ์ฐ์ ๋ฐ๋ณตํ์ฌ ๋ชจ๋ ๋ถ๋ถ ์งํฉ์ ์ํํ ์ ์๋ค. ํ์ง๋ง
subset = 0์ธ ์์ ์ ์ข ๋ฃ๋๊ธฐ์ ๊ณต์งํฉ์ ์ํํ์ง ์๋๋ค.
๐ ์ฐธ๊ณ
- Tech Interview for developer
- [ํ๋ก๊ทธ๋๋ฐ ๋ํ์์ ๋ฐฐ์ฐ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํด๊ฒฐ ์ ๋ต] ๊ตฌ์ข ๋ง